The invention relates to a method and an apparatus for correcting errors in a stream of data by using a method of decoding a cross-interleaved Reed-Solomon code (CIRC).
There has been a demand for increased quality of audio recording and read back systems as well as of other types of communication.
One problem with recording media are the defects in the media resulting in areas with improperly recorded digital data or in data that cannot be read back reliably. As a result errors occur in the read back data as well as in transmissions of digital data. During recording, read back and transmission of digital data, errors occur in the digital data with some finite probability. The data is typically composed of binary units, a group of binary units (such as 8) makes up a data byte, and groups of bytes (such as 2) make up a data word. Additionally the data is arranged into blocks of data (such as 32 or 28 byte blocks).
There are two different types of errors. The first type is a single bit error which is the substitution of one of two possible values of a binary bit for its opposite value. Such errors usually occur randomly in a digital signal. A second type of error consists of a continuous sequence of erroneous bits. Such errors are referred to as burst errors. The length of these bursts and their frequency of occurrence are also random.
One error correction code that is typically used in compact audio discs is a so-called CIRC correction code. CIRC is an acronym for crossinterleaved Reed-Solomon code. The CIRC utilises a two-step process. In passing through a first encoder, 24 consecutive data bytes representing a data polynomial are divided by a generator polynomial. In this process, four parity bytes are added. The result is a block of 24 data bytes and 4 parity bytes (C1 code). This consecutive sequence of bytes is interleaved or dispersed among other encoded data bytes.
The interleaved data is passed through a second encoder. The second encoder is identical to the first except that the bytes are presented in a different sequence due to interleaving, parity bytes together with data bytes are being encoded, blocks of 28 bytes (28 data bytes plus 4 parity bytes) are being encoded instead of 24 byte blocks, and 4 additional parity bytes are added. The result of the second encoding process is a 32 byte block (C2 code) composed of 24 data bytes and 8 parity bytes.
In the case of the CIRC correction code, the encoding process of the (28, 24) Reed-Solomon code is performed for twenty-four data symbols (bytes), with each symbol consisting of 8 bits. In typical audio applications each audio sample comprises 16 bits and is formed of two symbols of 8 bits each. Thus, each 8-bit symbol is either the upper or lower side of an audio sample of one of the two channels of stereophonic audio data.
The encoded data is recorded optically and subsequently read back. After the encoded data is read back, there will likely be single bit or burst errors due to recording, read back or transmission problems.
Conventional error correction methods are known for use in decoding CIRC. Examples of such methods are disclosed in U.S. Pat. No. 4,546,474, U.S. Pat No. 4,476,562 and U.S. Pat No. 4,497,058. According to the conventional methods for decoding CIRC errors, the processing is run on the basis of a so-called erasure correction method. In the erasure correction method the location of error symbols is indicated by means of pointer information. Error correction is performed on this error symbol. In the case of above-mentioned C1 and C2 codes, detection and correction up to double errors can be performed. However, if the error location is already know, then error correction up to 4 erasures can be performed. Therefore, in order to raise the error-correction capability, the implementation of the erasure correction method for error correction has been preferred. In addition, the erasure correction method has been found to be particularly effective in correcting burst errors.
According to the conventional method used for decoding CIRC errors, correction of up to two errors is performed in the C1 decoder. If triple errors or more occur, which of course are not corrected, C1 pointer information is sent to the C2 decoder in the next stage, so that error correction is performed in the C2 decoder utilising C1 pointer information.
Multiple use of the CIRC correction codes in decoding leads to an increase in correction capability of error correction systems. However, conventional decoding methods (CIRC decoders) are incapable of multiple processing of blocks of CIRC codes. In order to solve this problem, one can either provide conventional CIRC decoders with additional means or devices which allow multiple processing or make conventional CIRC decoders useful for multiple processing.
One method (conventional CIRC decoder) for multiple processing of CIRC codes has been disclosed in U.S. Pat No. 4,852,099. The known method uses the erasure correction method to increase the correction capability of error correction systems. It is proposed to perform C1 decoding and C2 decoding twice in a specific order. That order, for example, might be, C1 decoding, followed by C2 decoding, followed by C1 decoding, and followed by C2 decoding.
According to this example, C1 code words are supplied to a C1 decoder in which actual decoding of the (32, 28) Reed-Solomon code is performed. Error correction of up to two errors is performed. If three or more errors are detected by the C1 decoder, a C1 pointer is set for all symbols in C1 code words. Then data and error pointers corrected by means of C1 decoder are further processed in a deinterleave processing stage. An output of the deinterleaver is supplied to the C2 decoder. Erasure correction of up to four erasures is executed in the C2 decoder utilising C1 pointer information. Upon completion of erasure correction in the C2 decoder the C1 pointer is cleared and no pointer information is transferred to the second C2 decoding cycle.
In a second cycle data from the C2 decoder is supplied to the interleaver that returns the data to the same arrangement as it was when it was reproduced. Thereafter, the processing in the second decoding cycle corresponds to the processing in the first decoding cycle. By using this decoding method, multiple processing of CIRC codes can be performed, but additional hardware (interleaver block) is needed.
Another method used in decoding CIRC utilising multiple processing of CIRC is disclosed in U.S. Pat No. 4,637,021. Error detection and error correction is achieved by processing blocks of digital data bytes with a C1 decoder and a C2 decoder. In order to maximise the rate at which data is processed, decoders C1 and C2 actually operate concurrently on data stored in a system memory with the C1 decoder operating on the data ahead of the C2 decoder. According to the disclosed decoding method of the CIRC correction code, error processing up to double-error correction is executed in C1 decoding in first stage, and double-error correction is executed in C2 decoding at next stage by referring to C1 pointer information that is derived from the C1 decoder. In this case, C1 pointer information is not used to increase the error correction capability of error correction systems. C1 pointer information is used to check the quality of the decoding process.
In the method according to the U.S. Pat No. 4,852,099, data bytes are read by means of C1 and C2 decoders from the system memory according to the following sequence. A first C1 decoder processes a C1 block of data bytes (32 bytes). A first C2 decoder then processes a C2 block of data bytes (28 bytes) that has already been processed by the C1 decoder; this concludes a first pass. A second C1 decoder processes data bytes that have already been processed by the first pass, and a second C2 decoder processes data bytes that have already been processed by the first pass and the second C1 decoder; this concludes a second pass. A decoder cycle comprises the execution of both, the first pass and the second pass. At the end of each decoder cycle, an address counter is incremented, and the decoder cycle is repeated. New data is immediately written into memory locations when the data (C1 block) in the input buffer is ready. Thus, during operation the reading of the four decoders continually advances through the memory until available data has been processed.
The method according to U.S. Pat No. 4,852,099 for use in decoding CIRC is implemented by utilising a deinterleaver implementation and a special method of controlling data. A deinterleaver block is provided in a system memory (256xc3x9732 bytes) and consists of two blocks, a C1 memory block (128xc3x9732 bytes) and a C2 memory block (128xc3x9732 bytes). The C1 memory block includes addresses in rows 112 to 239. C2 memory block includes addresses in rows 240 to 255 and then in rows 0 to 111. The system memory is circular. The lowest numbered system memory address xe2x80x9cfollowsxe2x80x9d the highest numbered one. This is depicted in FIG. 1.
According to the known method, the first C1 decoder processes the C1 memory block of 32 data bytes. The C1 decoder is initially positioned to read the C1 memory block at address 112. In each succeeding decoder cycle (execution of two passes by both, C1 and C2 decoders), the C1 decoder is positioned to read the C1 memory block at the next successively higher address. Thus, for the second cycle the C1 memory block is positioned at position 113.
The first C2 decoder processes a C2 memory block of 28 data bytes. The C2 decoder is initially positioned to read the C2 memory block at address 0 of the system memory. Those bytes building the C2 memory block are arranged along a diagonal of the system memory (see FIG. 1). Those bytes building the C2 memory block are changed into successive decoding cycles.
At the beginning of the second C1 pass, the C1 decoder is positioned to read the C1 memory block at address 240 of the system memory. At the beginning of the second C2 pass, the C2 decoder is initially positioned to read the C2 memory block at address 113 of the system memory. The execution of four decoding passes (one decoder cycle) continually advances through the system memory. If unprocessed data is still in the system memory, the decoding cycles are continued. If all data in the system memory is corrected, the operation of the error correction system is completed.
The method for decoding CIRC correction codes as described above has the following disadvantages:
a) Data in the system memory is processed during 256 cycles (four decoding passes in each decoder cycle). If all data in the system memory is corrected, the operation of error correction system is completed. When sufficient data is available in the input buffer, an interruption in the system memory processing occurs in order to allow the C1 memory block to be written into the system memory. Interruptions can occur several times during the system memory processing (256 cycles). Therefore, any data in the the system memory can""t be processed twice (first C1, C2 passes and second C1, C2 passes).
b) Two decoders (C1 decoder and C2 decoder) need to be used concurrently on data stored in the system memory. Therefore, additional hardware is necessary.
c) The erasure correction method for Reed-Solomon codes cannot be used in conjunction with the method described above.
It is an object of the invention to disclose a method and an apparatus for use in decoding cross-interleaved Reed-Solomon code (CIRC) that efficiently corrects errors in a stream of data while hardware expenses are reduced.
It is another object of the invention to provide a method and an apparatus for use in decoding cross-interleaved Reed-Solomon code (CIRC) that corrects errors in a stream of data by utilising the so-called erasure correction method.
According to one aspect of the invention an error correction method is provided for use in a process of decoding cross-interleaved Reed-Solomon codes (CIRC) that corrects errors in data stored as C1-code words C1_CDWk (k=0, . . . , 108) and C2-code words C2_CDWm (m=0, . . . , 108) in a memory block with several locations Nij (i=0, . . . , 217; j=0, . . . , 31), each of said locations Nij containing a data byte of said data, the method comprising the following steps:
a1) reading and decoding said C1-code words C1_CDWk from said locations Nij utilising decoder means on the basis of
C1_CDWkj=Nij,
for k=0, . . . , 108 and j=0, . . . , 31, where i=k+109 and where C1_CDWkj is a data byte at position j in said C1-code word C1_CDWk;
a2) correcting said C1-code words C1_CDWk at least partially;
b1) reading and decoding said C2-code words C2_CDWm from said locations Nij utilising said decoder means on the basis of
C2_CDWmj=Nij,
for m=0, . . . , 108 and j=0, . . . , 28, where i=m+4*j and where C2_CDWmj is a data byte at position j in said C2-code word C2_CDWm; and
b2) correcting said C2-code words C2_CDWm at least partially.
This method provides reading and decoding of C1 and C2 code words in a novel manner. This means that the new method implies specific regulations for defining which data words are to be used for C1 and C2 decoding and for the processing order. The system memory for a deinterleaver implementation can be of a smaller size as compared to conventional system memories. In addition, only a single CIRC decoder needs to be used for performing the method according to the invention.
The correction of a large burst error in C1 code words can be executed very efficiently for a low input error rate.
According to another aspect of the invention a novel apparatus for running the above-provided error correction method is also provided.